import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Description: 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * @Date:Create in 11:11  2022/7/12
 */
public class isValid0020 {

    public static void main(String[] args) {
        String s = "(){}}{";
        System.out.println(isValid2(s));
    }

    //栈 暴力解法
    public static boolean isValid1(String s) {
        if(s.equals("")) return true;
        Stack<Character> sta = new Stack<>();
        int size = s.length();
        sta.push(s.charAt(0));
        int i = 1;
        for(;i<size;i++){
            if (s.charAt(i) == ')' && !sta.isEmpty()) {
                char a = sta.peek();
                if(a=='('){
                    sta.pop();
                    continue;
                }
                else return false;
            }else if(s.charAt(i) == ']' && !sta.isEmpty()){
                char a = sta.peek();
                if(a=='['){
                    sta.pop();
                    continue;
                }
                else return false;
            }else if(s.charAt(i) == '}' && !sta.isEmpty()){
                char a = sta.peek();
                if(a=='{'){
                    sta.pop();
                    continue;
                }
                else return false;
            }
            sta.push(s.charAt(i));
        }
        if(sta.isEmpty()) return true;
        else return false;
    }

    //deque 相当于栈
    public static boolean isValid2(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for(int i=0;i<s.length();i++){
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if(ch=='('){
                deque.push(')');
            }else if(ch=='['){
                deque.push(']');
            }else if(ch=='{'){
                deque.push('}');
            }else if(deque.isEmpty() || deque.peek() !=ch){
                return false;
            }else {
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
}
